本场链接:Codeforces Round #571

闲话

本场$B$是个错题,因此没有,而且ACD其实都比较简单,不过因为我思路和代码实现上能力的不足还是掉了一个档次.

A. Vus the Cossack and a Contest

原题大意:每个小孩要拿到一个铅笔和一个本子,两种各有$a$个和$b$个,问是否可以分配给所有小孩.

思路

水题,最小值就完事了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	int n,a,b;scanf("%d%d%d",&n,&a,&b);
	if(n <= min(a,b))	puts("Yes");
	else puts("No");
    return 0;
}

C. Vus the Cossack and Strings

原题大意:给定两个二进制字符串$a$和$b$,保证$|b| \leq |a|$.现找出$a$里从第一位开始的,所有长度和$b$的长度相等的连续的子串$c$,计算所有的$f(b,c)$,其中$f(b,c)$的值定义为$b$串和$c$串里不同的数的个数.输出所有的$f(b,c)$中值为偶数的数量.
数据范围:
$1 \leq |a| \leq 10^6$

错解思路

首先从复杂度上来说,肯定是只能有$O(N)$或者多加一个$log$的.显然不可能去比较两个整串的信息,复杂度上吃不消,但是又要统计一个连续区间上的信息,理所当然的就能想到应该是前缀和.但是前缀和怎么统计一段区间里有多少个数是不同的呢?我最开始的想法是先给所有的在$i$位置上的字符加上一个跟$i$有关的权重,再计算$b$串对应的权重,以及$b$每移动一次会变多少.这三个部分都是非常好计算的,而且也满足前缀和的求和,但是问题就是:还是没解决怎么判断有多少个相同的问题.前缀和的思路应该是没有问题的,但是加权重肯定不行,说明可能少了什么条件.

正解思路

前缀和确实没问题,但是少了一个性质.先来看一个特殊情况:假如说$c$里和$b$里的$1$的个数相同的话,那么不管怎样,不同的位数一定是偶数.
这一条性质可以这样感性的理解:首先如果对齐上下两边的$1$,那么整个串不同的个数必然是$0$,因为完全相同.其次如果没有任何一个$1$和另外一边的$1$上下同位的话,构成的不同的数量也必然是偶数,因为总的不同的数要乘$2$,进一步地,不管怎样安排,只要是某个$1$构成了不同,那么另外一个位置上的某个数也就必然因为位置不同而产生一个不同的相邻位置,因此必然是偶数.
简单归纳一下:如果完全相同,就是$0$.如果有一个不同,必然造成另外一个位置也跟着不同,所以总数永远是偶数.这就说明了:如果两边串$1$的个数相同,就一定说明两边不同的字符的数量是偶数.

但是实际情况还复杂得多,这个性质还需要进一步的推广:如果我在相同的两个串中的其中一个里,把偶数个$0$替换成$1$(例如0000011我替换掉偶数个变成1100011),那么整个性质依然是不变的,因为它相当于加了固定的两个不同的位置,对结果来说就是固定的$+2$,只要原来是偶数,现在依然是偶数;而另一种情况,也就是替换奇数的时候,显然就是不对的了,因为奇数肯定会导致结果也变成奇数.以上说明这个性质还可以推广成这样:如果两边的$1$的个数的奇偶性相同,那么不同的位置的数量就是偶数.

有了这个性质之后,显然用前缀和维护一下就可以求得数量并比较了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+7;
char a[N],b[N];
ll sa[N],sb,db;
int main()
{
	scanf("%s",a + 1);getchar();
	scanf("%s",b + 1);getchar();
	int n = strlen(a + 1),m = strlen(b + 1);
	for(int i = 1; i <= n;++i)	sa[i] = sa[i - 1] + (a[i] == '1');
	for(int i = 1; i <= m;++i)	sb += (b[i] == '1');
	int res = 0;
	for(int i = m;i <= n;++i)	
		if((sa[i] - sa[i - m]) % 2 == sb % 2)
			++res;
	printf("%d",res);
    return 0;
}

D. Vus the Cossack and Numbers

题目大意:有$n$个实数,他们的总和是$0$.现在要求你构造一个$n$个数的序列$b$,要求:
①$\sum b_i = 0$
②$b_i = \lceil a_i\rceil$或$b_i = \lfloor a_i\rfloor$
构造一个$b$的具体方案并输出,如果有多解,只输出一个.

错解思路

因为所有的$\sum a_i = 0$,所以对于每一个$a$的元素来说,如果每个元素都四舍五入,应该是满足条件的,因为对于一个比$0.5$大的部分一定对应着一个小于$-0.5$的部分,不然这整个和不可能是$0$.

错解代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	int n;scanf("%d",&n);
	vector<int> res;
	for(int i = 1;i <= n;++i)
	{
		double x;scanf("%lf",&x);
		int flag = 1;
		if(x < 0)	flag = -1,x = -x;
		int p = x;
		x -= p;
		x *= 10;
		// cout << x << endl;
		int r = (x + 5) / 10;
		if(r)	++p;
		res.push_back(p * flag);
	}
	for(auto& v : res)	printf("%d\n",v);
    return 0;
}

错解分析

这一切都看起来挺好的,因为和一定是$0$所以我把大的变得更大,小的变得更小,总之一切对齐.但是这不能解决一些边角情况,比如下面这个:

4
1.6
-1.4
-0.1
-0.1

他会把里面的$-0.1$错误的变成$0$.这个问题的来源主要是:这些对应的数不一定就是一一对应的,他可能是很多个和一起对应的,就是原来我想的是$1.6$应该就和一个负的上取整的数对应,但是$-1.4$不是直接上取整的,只有当他和那两个$-0.1$一起结合的时候才是对的,这样拆开来看就把这种情况错误的对应起来了.

正解思路

再往:多个数组合的思路上靠是没结果的,因为复杂度很显然不允许你去枚举多个数的和再去干别的事.因此要从单个数上考虑:注意原题的一句描述:For each i, |ai−bi|<1 must be met.这句话实际上启发我们,对于一个$b_i$而言,如果他就是一个整数,那么上下取整没区别,如果是一个小数,那么下取整与上取整的差距,必然是$1$.这句话有什么作用呢?如果我把所有的下取整的和先统计出来,对于一个是小数的$b_i$来说,那么他从下取整到上取整,必然能使整个和增加$1$.直到整个和为$0$.因此这个题的思路就是:先统计出所有的下取整的和,再枚举每个数,看他是不是携带有小数的实数,如果是的话,让他上取整,之后让和增加一直到和是$0$为止.并且下取整和必然是$\leq 0$的,所以不用担心别的问题.直接做就可以.
不过这题如果手动写上下取整会非常蛋疼,我一开始不知道$ceil/floor$是可以对负数用的搞了半天.如果用的话很快就能写掉这个D了.注意是否是整数的判断就是看$ceil$是否和他相等.

正解代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
double a[N];
int main()
{
	int n;scanf("%d",&n);
    ll downsum = 0;
    for(int i = 1;i <= n;++i)
    {
    	scanf("%lf",&a[i]);
    	downsum += (int)floor(a[i]);
    }
    if(downsum == 0)
    {
    	for(int i = 1;i <= n;++i)	
    		printf("%d\n",(int)floor(a[i]));
    }
    else
    {
    	for(int i = 1;i <= n;++i)
    	{
    		if((int)ceil(a[i]) == a[i])	
    			printf("%d\n",(int)a[i]);
    		else if(downsum == 0)
    		{
    			printf("%d\n",(int)floor(a[i]));
    		}
    		else
    		{
    			printf("%d\n",(int)ceil(a[i]));
    			++downsum;
    		}
    	}
    }
    return 0;
}